//
// Description: 20. 有效的括号
// Created by Loading on 2025/5/25.
//

#include <bits/stdc++.h>

using namespace std;

bool isValid(string s) {
    // 长度为奇数
    if (s.size() % 2 == 1) {
        return false;
    }

    unordered_map<char, char> kv = {
            {')', '('},
            {']', '['},
            {'}', '{'}
    };

    stack<char> st;
    for (auto c : s) {
        if (kv.count(c)) {
            if (st.empty() || st.top() != kv[c]) { // 未配对
                return false;
            }
            st.pop();
        } else {
            st.push(c);
        }
    }

    return st.empty();
}

int main() {
    string s = "[][]()}{";

    auto res = isValid(s);

    cout << res << endl;

    return 0;
}
